#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

#define LEN 20
typedef struct Node {
    int weight;
    char code[LEN];
    Node* left;
    Node* right;
} Node,*nodep;

void printNodes(nodep nodes[],int len){
    cout<<"============"<<endl;
    for(int i = 0;i<len;i++){
        cout<<i<<":"<<nodes[i]->weight<<endl;
    }
    cout<<"============"<<endl;
}

void createNodes(nodep root,nodep nodes[],int datas[],int len){
    for(int i = 0;i <len; i++){
        nodes[i] = new Node();
        nodes[i]->weight = datas[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }
    // printNodes(nodes,len);
}

void sortNodesDesc(nodep nodes[],int index){
    //sort desc by nodes' weight
    int flag = 1;
    for(int i = 0;i<index-1;i++){
        flag = 1;
        for(int j = 0;j<index-1-i;j++){
            if(nodes[j]->weight<nodes[j+1]->weight){
                nodep temp = nodes[j];
                nodes[j] = nodes[j+1];
                nodes[j+1] = temp;
                flag = 0 ;
            }
        }
        if (flag)
        {
            return;
        }
    }

}
void printNode(nodep node){
    cout<<"node : "<<node->weight<<endl;
}

void createTree(nodep &root,nodep nodes[],int len){
    //手动实现栈
    int size = len;

    while(size>0){
        //降序排序
        sortNodesDesc(nodes,size);
        // printNodes(nodes,size);
        // cout<<"size :"<<size<<endl;
        if(size == 1){
            // printNodes(nodes,size);
            root = nodes[0];
            size--;
        }else{
            //取最小的两个
            
            nodep left = nodes[size-2];
            nodep right = nodes[size-1];
            //出栈
            nodes[size-1] = NULL;
            nodes[size] = NULL;
            // printNode(left);
            // printNode(right);
            //创建新节点
            nodep newNode = new Node();
            newNode->weight = left->weight + right->weight;
            if (left->weight < right->weight){
                newNode->left = left;
                newNode->right = right;
            }else{
                newNode->left = right;
                newNode->right = left;
            }
            //入栈
            nodes [size-2] = newNode;
            size--;
        }
    }
}
void printTree(nodep root){
    if(root != NULL){
        cout<<root->weight<<endl;
        printTree(root->left);
        printTree(root->right);
    }
}

void getHuffmanCode(nodep root){
    if(root == NULL) return;

    nodep p = root;
    queue<nodep> q;
    q.push(p);
    while(q.size()>0){
        p = q.front();
        q.pop();
        if(p->left!=NULL){
            q.push(p->left);
            strcpy((p->left)->code, p->code);
            char *ptr = (p->left)->code;
            while (*ptr != '\0'){
                    ptr ++;
            }
            *ptr = '0';
        }
        if(p->right!=NULL){
            q.push(p->right);
            strcpy((p->right)->code, p->code);
            char *ptr = (p->right)->code;
            while (*ptr != '\0'){
                    ptr ++;
            }
            *ptr = '1';
        }
    }

}

void printLeaf(nodep root){
    if(root != NULL){
        printLeaf(root->left);
        if(root->left == NULL && root->right == NULL)
            cout<<root->weight<<":"<<root->code<<endl;
        printLeaf(root->right);

    }
}

int main(){
    nodep root;
    int len = 6;
    int datas[len] {1,2,3,4,5,6};
    nodep nodes[len];
    createNodes(root,nodes,datas,len);
    printNodes(nodes,len);
    createTree(root,nodes,len);
    printTree(nodes[0]);

    getHuffmanCode(root);
    printLeaf(root);

    

}